home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / lib / include / list.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-08-29  |  8.9 KB  |  281 lines
  1. /*
  2.  * list.h --
  3.  *
  4.  * Structures, macros, and routines exported by the List module.
  5.  *
  6.  * Copyright (C) 1985, 1988 Regents of the University of California
  7.  * Permission to use, copy, modify, and distribute this
  8.  * software and its documentation for any purpose and without
  9.  * fee is hereby granted, provided that the above copyright
  10.  * notice appear in all copies.  The University of California
  11.  * makes no representations about the suitability of this
  12.  * software for any purpose.  It is provided "as is" without
  13.  * express or implied warranty.
  14.  *
  15.  * rcsid "$Header: /sprite/src/lib/include/RCS/list.h,v 1.5 91/02/04 09:55:36 ouster Exp $ SPRITE (Berkeley)"
  16.  */
  17.  
  18. #ifndef _LIST
  19. #define _LIST
  20.  
  21. #ifndef _SPRITE
  22. #include "sprite.h"
  23. #endif
  24.  
  25. /*
  26.  * This module defines the list abstraction, which enables one to link
  27.  * together arbitrary data structures.  Lists are doubly-linked and
  28.  * circular.  A list contains a header followed by its real members, if
  29.  * any.  (An empty list therefore consists of a single element, the
  30.  * header,  whose nextPtr and prevPtr fields point to itself).  To refer
  31.  * to a list as a whole, the user keeps a pointer to the header; that
  32.  * header is initialized by a call to List_Init(), which creates an empty
  33.  * list given a pointer to a List_Links structure (described below).
  34.  * 
  35.  * The links are contained in a two-element structure called List_Links.
  36.  * A list joins List_Links records (that is, each List_Links structure
  37.  * points to other List_Links structures), but if the List_Links is the
  38.  * first field within a larger structure, then the larger structures are
  39.  * effectively linked together as follows:
  40.  * 
  41.  *          header
  42.  *      (List_Links)           first elt.            second elt.
  43.  *    -----------------    -----------------    ----------------- 
  44.  * ..->    |    nextPtr    | ---->    |  List_Links    | ---->    |  List_Links    |----..
  45.  *    | - - - - - - -    |    |        |    |        | 
  46.  * ..--    |    prevPtr    | <----    |        | <----    |        |<---..
  47.  *    -----------------    - ---  ---  ---    -    - ---  ---  ---    -
  48.  *                |    rest of    |    |    rest of    | 
  49.  *                |   structure    |    |   structure    | 
  50.  *                |        |    |        |
  51.  *                |      ...    |    |      ...    | 
  52.  *                -----------------    ----------------- 
  53.  * 
  54.  * It is possible to link structures through List_Links fields that are
  55.  * not at the beginning of the larger structure, but it is then necessary
  56.  * to perform pointer arithmetic to find the beginning of the larger
  57.  * structure, given a pointer to some point within it.
  58.  * 
  59.  * A typical structure might be something like:
  60.  * 
  61.  *      typedef struct {
  62.  *                  List_Links links;
  63.  *                  char ch;
  64.  *                  integer flags;
  65.  *      } EditChar;
  66.  *  
  67.  * Before an element is inserted in a list for the first time, it must
  68.  * be initialized by calling the macro List_InitElement().
  69.  */
  70.  
  71.  
  72. /*
  73.  * data structure for lists
  74.  */
  75.  
  76. typedef struct List_Links {
  77.     struct List_Links *prevPtr;
  78.     struct List_Links *nextPtr;
  79. } List_Links;
  80.  
  81. /*
  82.  * procedures
  83.  */
  84.  
  85. extern void    List_Init _ARGS_((List_Links *headerPtr)); 
  86.                 /* initialize a header to a list */
  87.  
  88. extern void    List_Insert _ARGS_((List_Links *itemPtr, List_Links *destPtr));
  89.                 /* insert an element into a list */
  90.  
  91. extern void    List_ListInsert _ARGS_((List_Links *headerPtr,
  92.                     List_Links *destPtr));
  93.                 /* insert a list into a list */
  94.  
  95. extern void    List_Remove _ARGS_((List_Links *itemPtr));
  96.                 /* remove an element from a list */
  97.  
  98. extern void    List_Move _ARGS_((List_Links *itemPtr, List_Links *destPtr));
  99.                 /* move an element elsewhere in a list */
  100.  
  101. /*
  102.  * ----------------------------------------------------------------------------
  103.  *
  104.  * List_InitElement --
  105.  *
  106.  *      Initialize a list element.  Must be called before an element is first
  107.  *    inserted into a list.
  108.  *
  109.  * ----------------------------------------------------------------------------
  110.  */
  111. #define List_InitElement(elementPtr) \
  112.     (elementPtr)->prevPtr = (List_Links *) NIL; \
  113.     (elementPtr)->nextPtr = (List_Links *) NIL;
  114.     
  115. /*
  116.  * Macros for stepping through or selecting parts of lists
  117.  */
  118.  
  119. /*
  120.  * ----------------------------------------------------------------------------
  121.  *
  122.  * LIST_FORALL --
  123.  *
  124.  *      Macro to loop through a list and perform an operation on each member.
  125.  *
  126.  *      Usage: LIST_FORALL(headerPtr, itemPtr) {
  127.  *                 / * 
  128.  *                   * operation on itemPtr, which points to successive members
  129.  *                   * of the list
  130.  *                   * 
  131.  *                   * It may be appropriate to first assign
  132.  *                   *          foobarPtr = (Foobar *) itemPtr;
  133.  *                   * to refer to the entire Foobar structure.
  134.  *                   * /
  135.  *             }
  136.  *
  137.  *      Note: itemPtr must be a List_Links pointer variable, and headerPtr
  138.  *      must evaluate to a pointer to a List_Links structure.
  139.  *
  140.  * ----------------------------------------------------------------------------
  141.  */
  142.  
  143. #define LIST_FORALL(headerPtr, itemPtr) \
  144.         for ((itemPtr) = List_First(headerPtr); \
  145.              !List_IsAtEnd((headerPtr),(itemPtr)); \
  146.              (itemPtr) = List_Next(itemPtr))
  147.  
  148. /*
  149.  * ----------------------------------------------------------------------------
  150.  *
  151.  * List_IsEmpty --
  152.  *
  153.  *      Macro: Boolean value, TRUE if the given list does not contain any
  154.  *      members.
  155.  *
  156.  *      Usage: if (List_IsEmpty(headerPtr)) ...
  157.  *
  158.  * ----------------------------------------------------------------------------
  159.  */
  160.  
  161. #define List_IsEmpty(headerPtr) \
  162.         ((headerPtr) == (headerPtr)->nextPtr)
  163.  
  164. /*
  165.  * ----------------------------------------------------------------------------
  166.  *
  167.  * List_IsAtEnd --
  168.  *
  169.  *      Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr
  170.  *      (i.e., itemPtr is the header of the list).
  171.  *
  172.  *      Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ...
  173.  *
  174.  * ----------------------------------------------------------------------------
  175.  */
  176.  
  177.  
  178. #define List_IsAtEnd(headerPtr, itemPtr) \
  179.         ((itemPtr) == (headerPtr))
  180.  
  181.  
  182. /*
  183.  * ----------------------------------------------------------------------------
  184.  *
  185.  * List_First --
  186.  *
  187.  *      Macro to return the first member in a list, which is the header if
  188.  *      the list is empty.
  189.  *
  190.  *      Usage: firstPtr = List_First(headerPtr);
  191.  *
  192.  * ----------------------------------------------------------------------------
  193.  */
  194.  
  195. #define List_First(headerPtr) ((headerPtr)->nextPtr)
  196.  
  197. /*
  198.  * ----------------------------------------------------------------------------
  199.  *
  200.  * List_Last --
  201.  *
  202.  *      Macro to return the last member in a list, which is the header if
  203.  *      the list is empty.
  204.  *
  205.  *      Usage: lastPtr = List_Last(headerPtr);
  206.  *
  207.  * ----------------------------------------------------------------------------
  208.  */
  209.  
  210. #define List_Last(headerPtr) ((headerPtr)->prevPtr)
  211.  
  212. /*
  213.  * ----------------------------------------------------------------------------
  214.  *
  215.  * List_Prev --
  216.  *
  217.  *      Macro to return the member preceding the given member in its list.
  218.  *      If the given list member is the first element in the list, List_Prev
  219.  *      returns the list header.
  220.  *
  221.  *      Usage: prevPtr = List_Prev(itemPtr);
  222.  *
  223.  * ----------------------------------------------------------------------------
  224.  */
  225.  
  226. #define List_Prev(itemPtr) ((itemPtr)->prevPtr)
  227.  
  228. /*
  229.  * ----------------------------------------------------------------------------
  230.  *
  231.  * List_Next --
  232.  *
  233.  *      Macro to return the member following the given member in its list.
  234.  *      If the given list member is the last element in the list, List_Next
  235.  *      returns the list header.
  236.  *
  237.  *      Usage: nextPtr = List_Next(itemPtr);
  238.  *
  239.  * ----------------------------------------------------------------------------
  240.  */
  241.  
  242. #define List_Next(itemPtr) ((itemPtr)->nextPtr)
  243.  
  244.  
  245. /*
  246.  * ----------------------------------------------------------------------------
  247.  *      The List_Insert procedure takes two arguments.  The first argument
  248.  *      is a pointer to the structure to be inserted into a list, and
  249.  *      the second argument is a pointer to the list member after which
  250.  *      the new element is to be inserted.  Macros are used to determine
  251.  *      which existing member will precede the new one.
  252.  *
  253.  *      The List_Move procedure takes a destination argument with the same
  254.  *      semantics as List_Insert.
  255.  *
  256.  *      The following macros define where to insert the new element
  257.  *      in the list:
  258.  *
  259.  *      LIST_AFTER(itemPtr)     --      insert after itemPtr
  260.  *      LIST_BEFORE(itemPtr)    --      insert before itemPtr
  261.  *      LIST_ATFRONT(headerPtr) --      insert at front of list
  262.  *      LIST_ATREAR(headerPtr)  --      insert at end of list
  263.  *
  264.  *      For example, 
  265.  *
  266.  *              List_Insert(itemPtr, LIST_AFTER(otherPtr));
  267.  *
  268.  *      will insert itemPtr following otherPtr in the list containing otherPtr.
  269.  * ----------------------------------------------------------------------------
  270.  */
  271.  
  272. #define LIST_AFTER(itemPtr) ((List_Links *) itemPtr)
  273.  
  274. #define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr)
  275.  
  276. #define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr)
  277.  
  278. #define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr)
  279.  
  280. #endif /* _LIST */
  281.